package 算法练习;/**
 * @author： li
 * @date： 2022-01-05 21:37
 * @version 1.0
 */

/*
 问题描述
 　　逗志芃在干了很多事情后终于闲下来了，然后就陷入了深深的无聊中。
 不过他想到了一个游戏来使他更无聊。他拿出n个木棍，然后选出其中一些粘成一根长的，
 然后再选一些粘成另一个长的，他想知道在两根一样长的情况下长度最长是多少。
 输入格式
 　　第一行一个数n，表示n个棍子。第二行n个数，每个数表示一根棍子的长度。
 输出格式
 　　一个数，最大的长度。
 样例输入
 4
 1 2 3 1
 样例输出
 3
 数据规模和约定
 　　n<=15
 */
import java.util.Scanner;
public class 无聊的逗01 {
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        /**在JDK中,
         整形类型是有范围的，最大值为Integer.MAX_VALUE，即2147483647，
         最小值为Integer.MIN_VALUE -2147483648。
        对整形最大值加1，2147483648（越界了），那么此时值为多少呢？
         结果是-2147483648，即是Integer.MIN_VALUE。
        类似的，对Integer.MIN_VALUE取反或者取绝对值呢？
         仍为Integer.MIN_VALUE，因为值为-2147483648，
         绝对值2147483648超过Integer.MAX_VALUE 2147483647。
        所以就有以下结果
        Integer.MAX_VALUE + 1 = Integer.MIN_VALUE
        Math.abs(Integer.MIN_VALUE) = Integer.MIN_VALUE （绝对值）
        Long，short，byte的结论是相同的。**/
        int ans=Integer.MIN_VALUE;
        int n = cin.nextInt();
        //n=4为例
        //1<<n 1的二进制为0000 0001 左移n位；1<<4=16
        int []array=new int[1<<n];
        int []nums=new int[n];
        for(int i=0;i<n;++i){
            nums[i]=cin.nextInt();
            array[1<<i]=nums[i];
        }
        cin.close();
//        for(int i=0;i<n;++i){
//            System.out.print(nums[i]+" ");
//        }
//        System.out.println(" ");
//        //0 1 2 0 3 0 0 0 1 0 0 0 0 0 0 0
//        for(int i=0;i<1<<n;++i){
//            System.out.print(array[i]+" ");
//        }
//        System.out.println(" ");
        for(int i=0;i<1<<n;++i){
            for(int j=0;j<n;++j){
                /*i 0<=i<16
                1<<j 1 2 4 8
                 continue:跳出本次for循环 执行下一次for循环
                i&(1<<j)相与等于0 表示array[0]不需要被赋值*/
                //if((i&(1<<j))==0) continue;
                int k= (int) Math.pow(2,j);
                if((i&k)==0)continue;
                //array[i]里的i表示array[i]的值是i的二进制数里的1的位数为第几根的和 比如i=3 0011 表示array[3]是由第一根和第二根的和
//                array[i]=array[i-(1<<j)]+nums[j];
                array[i]=array[i-k]+nums[j];
                System.out.println("i="+i);
                System.out.println("array "+(i-(1<<j)));
                System.out.println("j="+j);
                System.out.format("array[i]=%d",array[i]);
                System.out.println("---");
                break;
            }
        }
        for(int i=0;i<1<<n;++i){
            System.out.print(i+"  ");
        }
        System.out.println(" ");
        for(int i=0;i<1<<n;++i){
            System.out.print(array[i]+"  ");
        }
        System.out.println(" ");
        for(int i=1;i<(1<<n);++i){
            int j=(1<<n)-i-1;
            for(int k=j;k>0;k=(k-1)&j){
//                System.out.print("i:"+i+" "+"k:"+k+" ");
                if(array[k]==array[i])
                    ans=Math.max(array[k],ans);
            }
//            System.out.println(" ");
        }
        System.out.println(ans);

    }
}
/*
 * 1<<n表示1左移n位。代码是用二进制数的i位(1或0）来表示是否使用了第i根木棍。
 * 第一个for是输入数据和初始化array数组。
 * 第二个for是将array数组填满，array[i]的值是i的二进制数上所有为1的位对应的木棍的长度的和，
 * 如i的二进制数为0110则array[i]的值就是第二根木棍和第三根木棍长度的和。
 * 第三个for是遍历求值，i表示第一根合成木棍，j表示合成完i还剩哪些木棍可以用（i和j二进制数 相与& 为0，
 * 因为木棍不能重复使用，相或| 则为n位全1），k为第二根合成木棍，k的木材从j里面选取，i和k二进制数上的1就对应了他们是用哪些木棍合成的，
 * 最后求出两木棍等长情况中的最大值。*/